The KNN algorithm is the first supervised classification model we will study in depth. Its usefulness comes from its simplicity: to classify a new point, look at the k closest labeled training points and take a majority vote. This unit covers the algorithm's place in the taxonomy of ML methods, distance metrics, the critical choice of k, the equal-vote problem, and how weighted KNN fixes it.
Before looking at KNN itself, it helps to place it in the usual algorithm taxonomy. Two distinctions are relevant here: whether an algorithm is parametric or non-parametric, and whether it is a lazy or an eager learner. The two tables below compare them.
| Dimension | Parametric | Non-Parametric |
|---|---|---|
| Parameter count | Fixed, independent of data size | Grows with data size |
| Assumptions | Strong (linearity, normality, …) | Few / none |
| Examples | Linear Regression, Logistic Regression, Naïve Bayes | KNN, Decision Trees, Ensembles |
| Pros | Fast, require less data | Flexible, capture complex patterns |
| Cons | Too restrictive if assumptions fail | Need more data, computationally costly |
| Dimension | Lazy Learning | Eager Learning |
|---|---|---|
| Training phase | Stores the data only (zero compute) | Builds explicit model immediately |
| Work happens when? | Prediction time | Training time |
| Speed: train | Fast | Slow |
| Speed: predict | Slow (O(n) per prediction) | Fast |
| Example | KNN, case-based reasoning | Neural Networks, Linear Regression, Decsion Trees |
In the standard version of the algorithm, all selected neighbors have an equal say in the prediction. For a query instance whose class we want to predict, the procedure is:
Formally, KNN computes the estimated conditional probability that a query observation \(x_0\) belongs to class \(j\) as the fraction of points in its \(K\)-nearest neighborhood \(\mathcal{N}_0\) whose response equals \(j\):
where \(I(y_i = j)\) is an indicator function that equals \(1\) if the \(i\)-th neighbor belongs to class \(j\), and \(0\) otherwise. The observation \(x_0\) is then assigned to the class \(j\) with the largest estimated conditional probability.
A valid metric d must satisfy four axioms: non-negativity d(x1,x2) ≥ 0; self-proximity d(x,x) = 0; symmetry d(x1,x2) = d(x2,x1); and triangle inequality d(x1,x2) ≤ d(x1,x3) + d(x3,x2).
The Euclidean distance is the L2 norm, that is, the ordinary straight-line distance between two points in ℝⁿ.
It is the default metric for KNN in scikit-learn and matches the everyday notion of distance. It is also sensitive to feature scale, which is why the features must be standardized before it is used.
The Manhattan distance is the L1 norm, also called the city-block or taxicab distance. Instead of measuring a straight line, it adds the displacements along each axis.
It is more robust to outliers than the Euclidean distance, and it is often a better choice when the features have mixed types after encoding.
The Minkowski distance generalizes both of the previous metrics. The order p is an additional hyperparameter:
The value of k controls the complexity of the model. A small k lets the prediction follow every local detail of the training data, while a large k produces a smoother decision boundary. The table below shows how this trade-off behaves across the range of k.
| k | Model Complexity | Behavior | Risk |
|---|---|---|---|
| 1 (very small) | Highest | Memorizes every training point; jagged decision boundary | Overfit — sensitive to noise and outliers |
| 3, 5, 7 (odd) | High / Medium | Flexible, locally adaptive boundaries | Balanced (good default starting point) |
| ≈ √n or 10–20% of n | Moderate | Smoother boundaries | Underfit risk starts growing |
| n (all points) | Lowest | Always predicts the majority class — a trivial baseline | Underfit — ignores all local structure |
KNN decides everything on the basis of distance, so a feature measured on a large numerical scale will dominate the distance calculation even when it is not the more informative feature. The following example shows how large this effect can be.
Consider two points: Age=28 vs. 38, Salary=$100,000 vs. $150,000. Euclidean distance without scaling:
The salary difference of $50K completely dominates the 10-year age difference. After standardization, each feature is measured in SD units and both contribute fairly to the distance.
The figure below illustrates KNN in action on a simple dataset with six blue and six orange observations.
Left: A test observation (black cross) is shown. With K = 3, the three closest points (inside the circle) are identified. Two are blue and one is orange → the query is predicted as blue.
Right: The KNN decision boundary for K = 3 is shown in black. The blue grid indicates the region where a test point would be classified as blue; the orange grid indicates the region where it would be classified as orange.
The choice of K has a drastic effect on the decision boundary as shown in the following diagrma:
Small K → flexible, jagged boundaries, sensitive to noise (overfitting risk).
Large K → smooth, simple boundaries, ignores local patterns (underfitting risk).
The optimal K balances these two extremes, giving a boundary that captures true structure without memorizing noise.
In standard KNN each of the k neighbours gets exactly one vote, regardless of how far it is from the query point. This can produce counter-intuitive predictions, as shown below.
Suppose k = 5 for a new query point. The neighbours of Class A are at distances {0.1, 5.0}; the neighbours of Class B are at {4.8, 4.9, 5.1}. Standard KNN counts 3 B vs 2 A and predicts B. Yet the closest neighbour (distance 0.1) clearly belongs to A, and that strong evidence is completely ignored.
The natural solution is distance-weighted voting: assign a weight to each neighbour that decreases with distance, then sum weights per class and predict the class with the largest total.
A well-known formulation from the literature (Weighted k-Nearest-Neighbor Techniques and Ordinal Classification, 2004) defines a weighted scheme in which the distances of the nearest neighbours are first scaled relative to the local neighbourhood. The algorithm is:
Important distinction: \(D(i)\) is a normalised distance, not the final weight. A smaller \(D(i)\) means that the neighbour is closer. The weighting function \(f\) then converts that distance into a weight, typically giving a larger weight to a smaller distance.
Key advantage: Normalising by the \((K+1)\)-th distance expresses each neighbour's distance relative to the local neighbourhood scale.
One particularly simple choice is inverse-distance weighting, where the weight is inversely proportional to the neighbour's distance:
$$ w_i = \frac{1}{d_i}. $$This is the weighting used by sklearn.neighbors.KNeighborsClassifier when weights='distance'.
At first glance, this may look different from the normalised formulation above. However, when the weighting function is \(f(D)=1/D\), the two forms are equivalent for classification. Since
$$ D(i)=\frac{d_i}{d_{K+1}}, $$the inverse weight used in the 2004 formulation becomes
$$ w_i=\frac{1}{D(i)} =\frac{1}{d_i/d_{K+1}} =\frac{d_{K+1}}{d_i}. $$The factor \(d_{K+1}\) is the same for every one of the \(K\) neighbours. It therefore multiplies every weight by the same constant and does not change which class has the largest total weight. Thus, for inverse-distance weighting, we can equivalently use the much simpler formula
$$ \boxed{w_i=\frac{1}{d_i}}. $$Suppose K = 3, and the four nearest neighbours are at distances \(1, 2, 3,\) and \(4\). The fourth neighbour provides the \((K+1)\)-th distance used for normalisation.
| Neighbour | Distance \(d_i\) | Normalised Distance \(D(i)=d_i/4\) | Inverse Weight \(1/D(i)\) | Simple Weight \(1/d_i\) |
|---|---|---|---|---|
| 1st | 1 | 0.25 | 4.000 | 1.000 |
| 2nd | 2 | 0.50 | 2.000 | 0.500 |
| 3rd | 3 | 0.75 | 1.333 | 0.333 |
Notice that the normalised distance is smallest for the closest neighbour. This is exactly what we expect: the closest neighbour has the smallest distance.
We then apply the inverse function \(1/D\). This reverses the ordering, so the smallest distance produces the largest weight:
$$ 1/0.25=4,\qquad 1/0.50=2,\qquad 1/0.75\approx1.333. $$These are simply the ordinary inverse-distance weights multiplied by the same constant, \(4\):
$$ 4 = 4\times1,\qquad 2 = 4\times0.5,\qquad 1.333\approx4\times0.333. $$Therefore, the two sets of weights have exactly the same relative ordering and produce the same class prediction. The normalisation changes the numerical values of the weights, but not the outcome of the weighted vote.
This equivalence is specific to inverse-distance weighting. With other functions, such as a triangular or Gaussian function, applying the function to the normalised distance \(d_i/d_{K+1}\) is generally not the same as applying it directly to the raw distance \(d_i\).
The customer example below uses the simple inverse-distance formulation because it is straightforward to compute and is the form used by scikit-learn for weights='distance'.
Using the scaled customer dataset and query point David, with K = 3. As in the equivalence example above, we look one neighbour beyond K — the 4th nearest neighbour — purely to provide the standardising distance, not to vote.
| Neighbour | Distance \(d_i\) | Standardised Distance \(D(i) = d_i / d_{(K+1)}\) | Similarity Weight \(1/D(i)\) | Class |
|---|---|---|---|---|
| John | 0.349 | 0.362 | 2.759 | Yes |
| Rachael | 0.366 | 0.380 | 2.631 | No |
| Norah | 0.731 | 0.759 | 1.317 | Yes |
| Jefferson | 0.963 | NA — used only to standardise | NA | No |
| Ruth | 1.157 | NA — outside K+1 | NA | No |
The weighted prediction is Yes, and here it agrees with the simple majority vote — but the weighted scores show how much more strongly the evidence favours Yes than a simple 2-vs-1 count would suggest, since John and Norah's votes carry substantially higher weight than Rachael's alone.
Note: This example uses standardised distance (dividing by the (K+1)-th neighbour's distance) rather than raw \(1/d_i\), because the goal here is to demonstrate the general normalisation procedure that works for any kernel (triangular, Gaussian, etc.), not just the inverse-distance special case shown in Section 2.8's equivalence box. If you only ever plan to use \(1/d_i\) weighting, the standardisation step can be skipped, as shown earlier — but we keep it here to model the general-purpose workflow.
The strengths and weaknesses below follow directly from the properties discussed in this section: KNN is non-parametric and lazy, and it works entirely through distances.
Given a tiny 2-D training set. Compute for yourself, then reveal.
| Point | X | Y | Class |
|---|---|---|---|
| P1 | 0.3 | 0.7 | A |
| P2 | 0.2 | 0.9 | B |
| P3 | 0.6 | 0.6 | A |
| P4 | 0.5 | 0.1 | A |
| P5 | 0.7 | 0.7 | B |
| P6 | 0.4 | 0.9 | B |
| Query Q | 0.2 | 0.6 | ? |
d(Q, P₁) = √[(0.3−0.2)² + (0.7−0.6)²] = √(0.02) ≈ 0.141 (A)
d(Q, P₂) = √[(0.0)² + (0.3)²] = 0.300 (B)
d(Q, P₃) = √[(0.4)² + (0.0)²] = 0.400 (A)
d(Q, P₄) = √[(0.3)² + (0.5)²] = √(0.34) ≈ 0.583 (A)
d(Q, P₅) = √[(0.5)² + (0.1)²] = √(0.26) ≈ 0.510 (B)
d(Q, P₆) = √[(0.2)² + (0.3)²] = √(0.13) ≈ 0.361 (B)
Predictions: (a) k = 3 standard KNN (b) k = 5 standard KNN.
Sorted distances: {0.141 (A), 0.300 (B), 0.361 (B), 0.400 (A), 0.510 (B), 0.583 (A)}
(a) k = 3 neighbors: {A, B, B} → majority B → Predict Class B.
(b) k = 5 neighbors: {A, B, B, A, B} → 3 B, 2 A → Predict Class B.
Two features: house_sqft (range 800–4,000) and num_bedrooms (range 1–6).
House X: 1,200 sqft, 2 beds. House Y: 1,800 sqft, 3 beds.
Without any scaling, d(X,Y) ≈ √(600² + 1²) ≈ 600 — the bedroom difference is invisible.
(a) Standardization rescales each feature to SD units. Typical SDs: sqft ≈ 700, bedrooms ≈ 1.2. SD units difference: sqft 600/700 ≈ 0.86 SD, bedrooms 1/1.2 ≈ 0.83 SD. After standardization, both features contribute approximately equally to the distance — exactly what we want.
(b) No. Manhattan on raw data still sums: 600 + 1 = 601. The bedroom difference still vanishes. All distance metrics need scale alignment when feature scales differ.
Query point Q. K = 5. Distances and classes of nearest 5: { d=0.05 A, d=0.98 B, d=0.99 B, d=1.00 B, d=1.01 A }.
(a) Standard KNN counts: 3 B vs. 2 A → Predict B.
(b) Weights: A gets 1/0.05 + 1/1.01 ≈ 20 + 0.99 = 20.99. B gets 1/0.98 + 1/0.99 + 1/1.00 ≈ 1.02 + 1.01 + 1.00 = 3.03. Weighted sum A > B → Predict A.
(c) Difference arises because that one extremely close neighbor at d = 0.05 is a very strong signal for A. Weighted KNN is more sensible here because it respects proximity. Always compare weights='uniform' vs. weights='distance' in cross-validation.
Note: we skip the K+1 normalization step here since w = 1/d is the special case where it's mathematically redundant — normalizing by the 6th neighbor would only rescale every weight by the same constant, leaving the ranking and prediction unchanged (see Section 2.8). For any other kernel, always normalize first.
Two 4-dimensional standardized points: p = [0.1, −0.3, 0.5, 0.0] and q = [0.3, 0.1, −0.2, 0.7]. Compute (a) Manhattan distance, (b) Euclidean distance, and (c) Minkowski distance with p = 3.
First, coordinate-wise differences: p − q = [−0.2, −0.4, 0.7, −0.7]. Absolute values: |p − q| = [0.2, 0.4, 0.7, 0.7].
(a) Manhattan (L1): sum of absolute values.
(b) Euclidean (L2): root of sum of squares.
(c) Minkowski with p = 3: (sum of absolute differences cubed)^(1/3).
K = 4 (deliberately even, so ties can happen). Four nearest neighbors of a query: {d=0.2 → class 0, d=0.3 → class 1, d=0.5 → class 0, d=0.6 → class 1}.
(a) Standard KNN counts: 2 votes for class 0, 2 votes for class 1 → tie 50/50. Common tiebreakers: (i) pick the class of the single nearest neighbor (class 0 wins); (ii) use weighted KNN; (iii) prefer the class with higher overall prior in the whole training set; (iv) randomly sample (weak!).
(b) Weights per neighbor: w(0@0.2) = 5; w(1@0.3) ≈ 3.333; w(0@0.5) = 2; w(1@0.6) ≈ 1.667. Sums: Class 0 total = 5 + 2 = 7; Class 1 total ≈ 3.333 + 1.667 = 5.00.
Yes — weighting cleanly resolves the tie in favor of the closer class-0 neighbors.
Note: we skip the K+1 normalization step here since w = 1/d is the special case where it's mathematically redundant — normalizing by the 5th neighbor would only rescale every weight by the same constant, leaving the ranking and prediction unchanged (see Section 2.8). For any other kernel, always normalize first.
You have 8 training points, 2-D. Two are mislabeled noise: one red in a blue cluster, one blue in a red cluster. Answer qualitatively with justifications:
(a) k = 1: The two mislabeled points each "own" a little Voronoi cell around themselves. Any query that lands nearer to them than to any correctly-labeled neighbor will be predicted wrong. The decision boundary becomes highly flexible and follows the training data very closely, making it extremely sensitive to local noise – this is the overfitting regime.
(b) k = 7 (out of 8): Every prediction is a near-majority vote over almost the whole dataset. The two noisy points contribute 2/7 of a vote to queries everywhere, shifting every prediction slightly but smoothly toward the wrong class. The decision boundary is very smooth but too simple – it fails to capture the true local cluster structure. This is the underfitting regime.
(c) k = 1 overfits – it memorizes the noise and produces erratic local predictions that are highly sensitive to individual points. k = 7 underfits – it oversmooths and ignores the meaningful local patterns in the data. The optimal k (e.g., 3 or 5) balances flexibility with smoothness, capturing the true structure without being overly sensitive to noise.
Two points on a 2-D standardized plane: a = (1.0, −0.5), b = (2.0, 1.5).
|Δx| = 1, |Δy| = 2.
(a)
(b) 3 ≥ 2.236 ≥ 2.080 ✓ holds. As p increases, the distance approaches the larger coordinate (2.0). Higher p values increasingly penalize the largest coordinate difference while reducing the influence of smaller differences. L2 (p=2) provides a balanced middle ground.
You are given an adult-income dataset with these features. For each column, say YES / NO / MAYBE for whether the described transformation should happen before KNN, with a one-sentence justification.
We have K = 4 neighbors with distances to query: {1.0, 2.0, 3.0, 4.0}. The (K+1) = 5th neighbor's distance is 5.0 (used for normalization).
(a) D = [1/5, 2/5, 3/5, 4/5] = [0.2, 0.4, 0.6, 0.8].
(b) w = 1 − D = [0.8, 0.6, 0.4, 0.2]. (Check: closer points have bigger weights ✓.)
(c) Weighted sums: Class 1 = 0.8 (neighbor 1) + 0.4 (neighbor 3) = 1.2. Class 2 = 0.6 (neighbor 2) + 0.2 (neighbor 4) = 0.8.
Answer all 5 questions. Click an option for instant feedback.
Your score: 0 / 5
weights='distance'.